#include<vector>
#include<string>
using namespace std;
//滑动窗口类型
/*
*题目描述
*给定一个含有 n 个正整数的数组和一个正整数 target 。
*找出该数组中满足其和 ≥ target 的长度最小的 
*连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0  
*/

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0, right = 0, sum = 0, minL = nums.size() + 1;
        while (right < nums.size()) {
            sum += nums[right];
            while (sum >= target) {//滑动窗口left指针出窗口时的判断
                minL = min(minL, right - left + 1);//更新结果
                sum -= nums[left];
                left++;
            }
            right++;
        }
        return minL == nums.size() + 1 ? 0 : minL;
    }
};//时间复杂度O(n)
//题目描述
/*
*给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
*/
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int hash[127] = { 0 };//利用了哈希表来辨别字符串中是否有重复字符
        int len = 0;
        for (int left = 0, right = 0; right < s.size(); right++) {
            hash[s[right]]++;
            while (hash[s[right]] == 2) {
                --hash[s[left++]];
            }
            len = max(len, right - left + 1);
        }
        return len;
    }
};

//题目描述
/*
*给定一个二进制数组 nums 和一个整数 k，假设最多可以翻转 k 个 0 ，则返回执行操作后 数组中连续 1 的最大个数 。
*/
//这道题的关键是将问题反转为：求最长的子数组，其中0的个数小于k
class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int len = 0, count = 0;
        for (int left = 0, right = 0; right < nums.size(); right++) {
            if (nums[right] == 0) count++;
            while (count > k) {
                if (nums[left++] == 0)count--;
            }
            len = max(len, right - left + 1);
        }
        return len;
    }
};
//题目描述
/*
*将x减到0的最小操作数
*给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，
*然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。
*如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。
*/
class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
        }
        int len = -1, k = sum - x, sumK = 0;
        if (k < 0) return -1;
        for (int left = 0, right = 0; right < nums.size(); right++) {
            sumK += nums[right];
            while (sumK > k) {
                sumK -= nums[left++];
            }
            if (sumK == k) len = max(len, right - left + 1);
        }
        return len == -1 ? -1 : nums.size() - len;
    }
};//这道题要注意更新结果这一操作的位置以及面临的几个特殊情况
